/* 3.2 Транзитивное замыкание */

#include <stdio.h>
#include <limits.h>

#define M INT_MAX/2

int main()
{
	int n = 6;
	int a[10][10] = {{0, 3, M, 2, M, 7},
			 {M, 0, M, M, M, M},
			 {8, M, 0, 1, 4, M},
			 {M, M, M, 0, M, 1},
			 {M, M, M, 2, 0, 5},
			 {M, M, M, M, 1, 0}};
	int i = 0, j = 0, k = 0;
	int way[10][10] = {0};
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
		{
			way[i][j] = i;
		}
	
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				if (a[i][j] > a[i][k] + a[k][j]) 
				{	
					a[i][j] = a[i][k] + a[k][j];
					way[i][j] = way[k][j];
				}
	/* print length */
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (a[i][j] == M) printf("M ");
			else printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	/* print way */
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (a[i][j] == M) printf("I ");
			else 
			{
				if (way[i][j] == i) printf("D ");
				else printf("%d ", way[i][j]);
			}
		}
		printf("\n");
	}	
	return 0;
}
